The present invention concerns an interleaving method and device used by systems for turbocoding or turbodecoding binary sequences, which may be of variable length, and systems using them.
It applies equally well to the coding of data representing a physical quantity, to the coding of data in the form of codes able to modulate a physical quantity, to the decoding of data-modulated signals, and to the decoding of data representing a physical quantity. These data can, for example, represent images, sounds, computer data, electrical quantities or stored data.
In general terms, a turbocoder uses at least two recursive convolutional coders and at least one permutation circuit also referred to as an interleaving circuit or interleaver. The corresponding iterative decoder is referred to as a turbodecoder.
Turbodecoders are nowadays envisaged for use in third-generation mobile systems, notably for certain data services.
On these subjects, documents served as a reference are, on the one hand, the article by Messrs. C. BERROU, A. GLAVIEUX and P. THITIMAJSHIMA entitled xe2x80x9cNear Shannon limit error-correcting coding and decoding: turbocodesxe2x80x9d published with the reports of the conference xe2x80x9cICC""93xe2x80x9d, 1993, pages 1064 to 1070, and on the other hand of the article by Messrs C. BERROU and A. GLAVIEUX entitled xe2x80x9cNear Optimum error-correcting coding and decoding: turbo-codesxe2x80x9d published by IEEE Transactions on Communication, Volume COM-44, pages 1261 to 1271, in October 1996.
The construction of permutation devices is far from being perfectly mastered. In general, this device uses square or rectangular matrices in which one row after another is written and one column after another is read. These matrices are generally very large, for example of size 256xc3x97256.
According to another method, in an article entitled xe2x80x9cWeight distributions for turbo-codes using random and nonrandom permutationsxe2x80x9d published by the Jet Propulsion Laboratory, with xe2x80x9cTDA Progress Reportxe2x80x9d, number 42-122, Aug. 15, 1995, Messrs. DOLINAR and DIVSALAR consider the permutations which, numbering the k information positions between 0 and kxe2x88x921, move the binary information placed at a position i to a position e i+f, for xe2x80x9cwell chosenxe2x80x9d values of e and f.
In this document, the authors give only one example where k is a power of 2. In addition, the authors do not discuss the possible mutual influence of the choice of the permutation device and the choice of the elementary convolutional coders (2, 1) to be used for generating the coded sequences produced by the turbocoder (3, 1).
The evaluation of one or more interleavers and a turbocode using them generally consists of simulating the use of the turbocode on a transmission channel with different values of the signal/noise ratio and measuring the minimum value of this ratio for which a predetermined error probability on the binary values is reached.
However, the use of simulations as an evaluation tool can lead to a few problems. In particular, the consequences of a non-return to zero are concealed.
For example, the permutation device will be considered with k=65536=256xc3x97256, mentioned above, and a predetermined error probability equal to 10xe2x88x925 will be chosen for simulating the performance of a turbocode using this device. Consequently, the mean number of errors on the binary values per block of 256xc3x97256 will be close to 1, but it will not be known whether each binary information item has the same error probability. This error probability could be fairly high for binary values having an xe2x80x9cunluckyxe2x80x9d position in the permutation device, and this probability could be much smaller for more xe2x80x9cluckyxe2x80x9d positions.
One possible method for remedying this situation is to produce a harmonious conjoint design of the permutation device and two convolutional coders in order to guarantee reasonable uniformity of the error rate on the binary values after decoding, according to the position of the binary information in the permutation device.
Another problem concerns the lack of algebraic tools for specifying the permutation devices. It could be useful to have available means for specifying a selection of permutation devices having performances representing the set of all the permutation devices.
The invention concerns mainly the transmission of information represented by sequences of binary symbols:
u=(u0, u1, . . . , ukxe2x88x921),
referred to as xe2x80x9cinformation sequencesxe2x80x9d, which will be coded as a triplet of binary sequences,
v=(a, b, c),
each of these sequences a, b and c, by itself, representing the sequence u.
In the remainder of the description, use is made indifferently, for representing a sequence u, of the form u=(u0, u1 , . . . , ukxe2x88x921), and the associated polynomial form:
u(x)=u0x0+u1x1+ . . . +ukxe2x88x921xkxe2x88x921.
Equivalent notations will be used for the sequences a, b and c. Using this second representation, it is known, for determining the triplet v=(a, b, c):
to choose a(x)=u(x);
to choose b(x)=u(x).h1(x)/g(x),
where g(x) is a polynomial, for example g(x)=1+x+x3, corresponding, according to the representation in sequence, to the sequence (1, 1, 0, 1); and h1(x) is a polynomial, for example h1(x)=1+x+x2+x3, corresponding to the sequence (1, 1, 1, 1); and
calling a* a sequence formed by permutation of the binary data of the sequence a, to choose c(x)=a*(x).h2(x)/g(x)
where h2(x) is a polynomial, for example h2(x)=(1+x2+x3) corresponding to the sequence (1, 0, 1, 1).
Any choice of the polynomials g(x), h1(x), h2(x) and of the permutation specifying the interleaver which associates the permuted sequence a* with the sequence a, specify the coder which will be referred to as a xe2x80x9cturbocoderxe2x80x9d. All the sequences which can produce a specified turbocoder will be referred to as a xe2x80x9cturbocodexe2x80x9d.
In the remainder of the description, the elementary recursive convolutional coder which produces the sequences b will be referred to as the xe2x80x9cfirst coderxe2x80x9d, and the one which produces the sequence c will be referred to as the xe2x80x9csecond coderxe2x80x9d.
The polynomial divisions used are of the division according to increasing powers type, well known to persons skilled in the art. They use modulo 2 arithmetic. The sequences a, b and c are binary sequences and in the general case the divisions which define b and c have a remainder.
This type of coding method has the advantage of lending itself to a high-performance iterative decoding, of low complexity and inexpensive.
For implementing the turbocoding, several questions arise:
I/ How to choose the polynomials g(x), h1(x) and h2(x)?
II/ How to choose the permutation of the terms of the sequence a which produces the sequence a*?
Amongst the choices proposed, three examples of interleavers, that is to say operators which permute the terms of the sequence a, in order to form the sequence a*, are given below:
A) in the first example, after having stored the terms of a in a rectangular table, successively row by row and, for each row, from left to right, the sequence a* is formed by taking the terms successively from this table column after column and, for each column, from top to bottom. For example, in the case of sequences of six terms and the use of a table of two rows of three columns, the interleaver transforms the sequence a =(a0, a1, a2, a3, a4, a5) into the sequence a*=(a0, a3, a1, a4, a2, a5).
B) in a second example, the i-th term (i=0, 1, 2, . . . ) a*i of the sequence a* is chosen as being the term aj of the sequence a, with j=s.i+t calculated modulo the number of terms of the sequence a, s and t being integers. For example, if the number of terms in the sequence a is six and if s=5 and t=3, the interleaver transforms the sequence a =(a0, a1, a2, a3, a4, a5) in the sequence a*=(a3, a2, a1, a0, a5, a4).
C) in the third example, the chosen permutation is random.
III/ How to avoid the division defining b(x) having a remainder? and
IV/ How to avoid the division defining c(x) having a remainder?
Replying to these last two questions amounts to resolving a problem frequently mentioned in the literature on turbocodes, which is that of the xe2x80x9creturn to the zero statexe2x80x9d of the elementary convolutional coders defining b and c. Since the turbocoders have two elementary recursive coders, the second of which uses a permutation a* of the sequence a, it is wished to guarantee that the polynomials a(x) and a*(x) representing the information sequence u(x) are simultaneously divisible by g(x). Ensuring this divisibility of a(x) is simple since it suffices to construct a(x) from u(x), supplementing u(x) with padding symbols, equal in number to the degree of g(x) whose sole function is to guarantee the absence of a remainder in the division used to produce b(x) from a(x).
Choosing a permutation using a*(x) from a(x) which guarantees both the divisibility of a*(x) by g(x) and good error correction performance for the turbocode thus specified is, on the other hand, more difficult.
This problem can give rise to disparities between the probabilities of errors after decoding the different bits constituting u(x).
In an article which appeared in Volume 31, No. 1 of the journal xe2x80x9cElectronics Lettersxe2x80x9d on Jan. 5, 1995, Messrs. BARBULESCU and PIETROBON disclosed that an interleaver can be described by successively and cyclically storing the terms of the sequence a in a number of sequences equal to the degree of the polynomial g(x) incremented by one, and that, in this case, permutations internal to each of the sequences thus formed give rise to equality between the remainder of the division defining the sequence b and that of the division defining the sequence c.
However, and contrary to what is said in this article, this statement is true only if the polynomial g(x) is of the form xcexa3i=0àmxi.
In an article entitled xe2x80x9cTurbo-block-codesxe2x80x9d published with the reports of the seminar xe2x80x9cTurbocodingxe2x80x9d organised by the Institute of Technology of Lund (Sweden) (Department of Applied Electronics) in August 1996, Messrs. C. BERROU, S. EVANO and G. BATTAIL disclosed that, by arranging the terms of the sequence u, cyclically, in a number of columns equal to a multiple of the degree NO of the polynomial of type xnxe2x88x921 with the lowest strictly positive degree which is divisible by g(x), permutations internal to each of the columns thus formed mean that the sum of the remainder of the division defining the sequence b and that of the division defining the sequence c is nil, so that the concatenation of the sequences is divisible by g.
This document, like the previous one, therefore restricts the choice of interleavers to particular forms working independently on subsets of the terms of the sequence a by applying internal permutations to them. It does not however guarantee that individually a(x) and a*(x) will be divisible by g(x). The only guarantee is the divisibility by g(x) of the polynomial representing the concatenation (a, a*), consisting of putting the two sequences a and a* end to end.
The result is a possible loss in efficiency of the decoder since the latter is not informed of the state which the coder had at the instant marking the end of the calculation of b and the start of the calculation of c.
None of the articles cited proposes an effective choice of interleaver.
With a view to mitigating these drawbacks, the inventors firstly developed a solution guaranteeing the return to zero not only of the control sequence coming from the first coder but also that issuing from the second coder. This solution must satisfy the following condition and is set out in the following paragraph:
A turbocoder with an efficiency of 1/3 can be considered as a pair of systematic convolutional coders (see FIG. 1) with divisor polynomials such that the first coder produces a control sequence from the sequence of symbols to be coded u and the second coder produces a control sequence from an interleaved sequence u* obtained by interleaving the sequence u. In this context, the simultaneous return to zero of two coders is a classic problem. A way of resolving it has been found by the inventors and is summarised below.
Let g(x) be the divisor polynomial of a turbocoder. Let m be the degree of the polynomial g(x) and N0 the smallest integer such that g(x) is a divisor of the polynomial xN0+1. This number N0 will be referred to as the xe2x80x9cperiodxe2x80x9d of g(x).
Let also n be a multiple of N0: n=M.N0.
A sequence of symbols, u, then has a polynomial representation, u(x), of degree nxe2x88x92mxe2x88x921, with binary coefficients, and this polynomial u(x) is pre-encoded as:
a(x)=u(x)+xcexa3i=nxe2x88x92mànxe2x88x921aixi
where the m binary symbols ai are chosen so that a(x) is a multiple of g(x).
In general terms, the inventors discovered that the interleavers guaranteeing return to zero, not only of the control sequence coming from the first coder but also of that issuing from the second coder, should meet the following conditions:
each xe2x80x9cpermutedxe2x80x9d sequence, aij*, (i=1, . . . , K; j=1, . . . , M1), is obtained by a permutation of the corresponding sequence ai, said permutation being, in a representation where the binary data of each sequence ai are written, row by row, in a table with N0 columns and M rows, N0 being the smallest integer such that each divisor polynomial gi(x) divides xN0+1, the resultant of any member of so-called elementary permutations which, each:
either has the property of transforming the cyclic code of length N0 and with generator polynomial gi(x) into an equivalent cyclic code with generator polynomial gij(x) which can be equal to gi(x), and acts by permutation on the N0 columns of the table representing ai,
or is any permutation of the symbols with a column in said table.
This method applies to blocks with a given length enabling each of the elementary coders to be reset to zero in a suitable fashion. However, the input sequence must have a certain length depending solely on the divisor polynomial or polynomials used. This must be a multiple of a number N0.
When the sequence of symbols to be coded does not correspond to this number (this is to say when the sequence of symbols to be coded, to which so-called xe2x80x9cpaddingxe2x80x9d symbols are added, which guarantee the divisibility of the polynomial representation of the resulting sequence, by a predetermined polynomial, as a length which is not a multiple of N0), the initial teaching of the inventors cannot be used directly. The same applies when the length of the sequence varies from one sequence to another.
In addition, the transmission conditions, the required efficiency, the type of data, the type of transmission channel and the signal/noise ratio of the channel are not taken into account, in the first stage of the invention made by the inventors, this first stage not forming part of the prior art of the present invention, but, quite the contrary, supplying essential characteristics thereof.
In addition, in a turbocoder, the sizing of the memory cannot be adapted easily to transmission modes taking into account different block lengths.
If the pseudo-random interleavers of the state of the art are considered, it is necessary to store all the interleavers liable to be used and the memory size required can be large.
The present invention aims to obtain a family of interleavers which offers good performance, low complexity and great flexibility for varied sizes which can range from 320 to 8192 bits.
For this purpose, it is notably important to have the property of preserving divisibility by the feedback generating polynomial used in the coders making up the turbocoders, or intrinsic return to zero property of the coders making up the turbocoder.
This property makes it possible to obtain the best performance in the case of small sizes of interleavers.
The present invention aims to remedy the drawbacks of the prior art, by providing a device and a method for interleaving binary data which define a family of interleavers having different sizes, and such that each of the interleavers in this family has optimum performance.
To this end, the invention proposes a method of interleaving binary symbols representing a physical quantity, used in a coding system with at least two recursive convolutional coders having respectively a divisor polynomial having a same given period or in the corresponding decoding system, characterised in that it includes operations of:
writing binary symbols in a table having a first number of columns equal to the period of the coders and a second number of rows,
first permutations of the symbols on each of the columns, and
second permutation of the columns with each other, said second permutation preserving the property of return to zero of the coders.
In this way good performance and great flexibility are obtained.
According to preferred alternative characteristics:
the first permutations are derived from each other, passing from one column to the next, by shifting modulo the second number,
the first permutations are derived from each other, passing from one column to the next, by a shifting which is substantially the same for all the columns,
the first permutations are derived from each other, passing from one column to the next, by a shifting which is the same for all the columns, when the second number is a multiple of the first number,
the first permutations are identical to each other.
These characteristics are simple to implement, whilst offering good performance.
According to other preferred alternative characteristics:
the first permutations are of the algebraic type, with at least one dimension,
the first permutations are obtained by extraction performed on an interleaver of larger size, which is for example a power of two,
the first permutations are pseudo-random.
These characteristics are simple to implement, whilst offering good performance.
According to other preferred alternative characteristics:
the second permutation is circular,
the columns being numbered in increasing binary numbers, the second permutation is circular on the bits of the column numbers.
These characteristics are simple to implement, whilst offering good performance.
The invention also relates to an interleaving device comprising means for implementing the above features.
The invention also relates to a coding method and a decoding method including the interleaving method previously disclosed.
The invention also concerns a coding device and a decoding device including means for implementing the above features.
The invention also relates to:
a device for processing signals representing speech, which includes a device as succinctly disclosed above,
a data transmission device including a transmitter adapted to implement a packet transmission protocol, which includes a device as succinctly disclosed above,
a data transmission device including a transmitter adapted to implement the ATM (asynchronous transfer mode) packet transmission protocol, which includes a device as succinctly disclosed above,
a data transmission device including a transmitter adapted to implement the packet transmission protocol on a network of the ETHERNET (registered trade mark) type,
a network station, which includes a device as succinctly disclosed above,
a data transmission device including a transmitter transmitting over a wireless channel, which includes a device as succinctly disclosed above, and
a device for processing sequences of signals representing at most one thousand binary data, which includes a device as succinctly disclosed above.
These coding and decoding devices, these coding and decoding methods and these signal processing, data transmission and sequence processing devices and this network having the same particular characteristics and the same advantages as the coding method as succinctly disclosed above, these particular characteristics and these advantages are not repeated here.
An information storage means, possibly partially or totally removable, which can be read by a computer or by a microprocessor, stores instructions of a computer program which makes it possible to implement the method of the invention as succinctly disclosed above.